package NO9_Graph;

import java.util.Arrays;

/**
 * 2025-09-02
 * 力扣 - 130. 被围绕的区域
 * <p>
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
 * 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
 * 区域：连接所有 'O' 的单元格来形成一个区域。
 * 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
 * 通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值
 */
public class SolveMain {
    public static void main(String[] args) {
        char[][] board =
                {
                        {'X', 'X', 'X', 'X'},
                        {'X', 'O', 'O', 'X'},
                        {'X', 'X', 'O', 'X'},
                        {'X', 'O', 'X', 'X'}
                };
        System.out.println(Arrays.deepToString(board));
        solve(board);
        System.out.println(Arrays.deepToString(board));
    }

    /**
     * - 处理边界上的'O'：
     * 首先遍历四条边界，如果发现'O'，
     * 就从这个点开始DFS/BFS，
     * 将所有相连的'O'标记为特殊字符（比如'#'）
     * - 处理内部区域：遍历整个网格
     * 剩下的'O'就是被完全包围的，将它们变成'X'
     * 将标记的'#'恢复为'O'
     */
    public static void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }

        int row = board.length;
        int col = board[0].length;

        // 1.处理第一列和最后一列
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col - 1);
            }
        }

        // 2.处理第一行和最后一行
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[row - 1][j] == 'O') {
                dfs(board, row - 1, j);
            }
        }

        // 3.遍历整个网格，处理剩余的'O'
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X'; // 被包围的'O'变成'X'
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O'; // 恢复边界相连的'O'
                }
            }
        }
    }

    // 处理边界上的'O'
    private static void dfs(char[][] board, int i, int j) {
        int rows = board.length;
        int cols = board[0].length;

        // 边界检查
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {
            return;
        }

        board[i][j] = '#';

        // 递归探索四个方向（上下左右）
        dfs(board, i + 1, j); // 向下
        dfs(board, i - 1, j); // 向上
        dfs(board, i, j + 1); // 向右
        dfs(board, i, j - 1); // 向左
    }
}
